package leecode

func pathSumM(root *TreeNode, sum int) int {
	if root == nil {
		return 0
	}
	res := backtrackingM(root, sum)
	res += pathSumM(root.Left, sum)
	res += pathSumM(root.Right, sum)
	return res
}

func backtrackingM(node *TreeNode, target int) int {
	var result int
	if node == nil {
		return result
	}
	target = target - node.Val
	if target == 0 {
		result++
	}
	result += backtrackingM(node.Left, target)
	result += backtrackingM(node.Right, target)
	target += node.Val
	return result
}
